
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n= matrix[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+2,0));
        for(int i=1;i<=m;i++)
        {
            dp[i][0] = dp[i][n+1] = INT_MAX;
        }
        for(int i =1;i<=m;i++)
        {
            for(int j =1;j<=n;j++)
            {
                dp[i][j] = min(min(dp[i-1][j-1],dp[i-1][j+1]),dp[i-1][j])+matrix[i-1][j-1];
            }
        }
        int mx = dp[m][1];
        for(int j=1;j<=n;j++)
        {
            if(dp[m][j]<mx)
            {
                mx = dp[m][j];
            }
        }
        return mx;
    }
};